A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance
Identifieur interne : 000C69 ( Main/Exploration ); précédent : 000C68; suivant : 000C70A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance
Auteurs : Daniel Binkele-Raible [Allemagne] ; Ljiljana Brankovic [Australie] ; Henning Fernau [Allemagne] ; Joachim Kneis [Allemagne] ; Dieter Kratsch [France] ; Alexander Langer [Allemagne] ; Mathieu Liedloff [France] ; Peter Rossmanith [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2010.
Abstract
Abstract: The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G) respectively, are conceptually linked to domination and independence numbers and have numerous relations to other graph parameters. It is a long-standing open question whether determining these numbers for a graph G on n vertices admits exact algorithms running in time less than the trivial Ω(2 n ) enumeration barrier. We solve this open problem by devising parameterized algorithms for the duals of the natural parameterizations of the problems with running times faster than $\mathcal{O}^*(4^{k})$ . For example, we present an algorithm running in time $\mathcal{O}^*(3.069^{k}))$ for determining whether IR(G) is at least n − k. Although the corresponding problem has been shown to be in FPT by kernelization techniques, this paper offers the first parameterized algorithms with an exponential dependency on the parameter in the running time. Furthermore, these seem to be the first examples of a parameterized approach leading to a solution to a problem in exponential time algorithmics where the natural interpretation as exact exponential-time algorithms fails.
Url:
DOI: 10.1007/978-3-642-13073-1_28
Affiliations:
- Allemagne, Australie, France
- Centre-Val de Loire, Grand Est, Lorraine (région), Rhénanie-Palatinat, Région Centre
- Metz, Orléans, Trèves (Allemagne)
- Université Paul Verlaine - Metz, Université de Trèves
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001B33
- to stream Istex, to step Curation: 001A16
- to stream Istex, to step Checkpoint: 000348
- to stream Main, to step Merge: 000D23
- to stream Main, to step Curation: 000C69
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance</title><author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name></author><author><name sortKey="Brankovic, Ljiljana" sort="Brankovic, Ljiljana" uniqKey="Brankovic L" first="Ljiljana" last="Brankovic">Ljiljana Brankovic</name></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><country>Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name></author><author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name></author><author><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name></author><author><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name></author><author><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:D53E1C54122748DE8921D66B3B2ABDDBDB118DD2</idno><date when="2010" year="2010">2010</date><idno type="doi">10.1007/978-3-642-13073-1_28</idno><idno type="url">https://api.istex.fr/document/D53E1C54122748DE8921D66B3B2ABDDBDB118DD2/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001B33</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001B33</idno><idno type="wicri:Area/Istex/Curation">001A16</idno><idno type="wicri:Area/Istex/Checkpoint">000348</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000348</idno><idno type="wicri:doubleKey">0302-9743:2010:Binkele Raible D:a:parameterized:route</idno><idno type="wicri:Area/Main/Merge">000D23</idno><idno type="wicri:Area/Main/Curation">000C69</idno><idno type="wicri:Area/Main/Exploration">000C69</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance</title><author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Brankovic, Ljiljana" sort="Brankovic, Ljiljana" uniqKey="Brankovic L" first="Ljiljana" last="Brankovic">Ljiljana Brankovic</name><affiliation wicri:level="1"><country xml:lang="fr">Australie</country><wicri:regionArea>The University of Newcastle, University Drive, NSW 2308, Callaghan</wicri:regionArea><wicri:noRegion>Callaghan</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Australie</country></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea><wicri:noRegion>RWTH Aachen University</wicri:noRegion><wicri:noRegion>RWTH Aachen University</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name><affiliation wicri:level="4"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Metz</settlement></placeName><orgName type="university">Université Paul Verlaine - Metz</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea><wicri:noRegion>RWTH Aachen University</wicri:noRegion><wicri:noRegion>RWTH Aachen University</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2</wicri:regionArea><placeName><region type="region" nuts="2">Centre-Val de Loire</region><region type="old region" nuts="2">Région Centre</region><settlement type="city">Orléans</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea><wicri:noRegion>RWTH Aachen University</wicri:noRegion><wicri:noRegion>RWTH Aachen University</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2010</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">D53E1C54122748DE8921D66B3B2ABDDBDB118DD2</idno><idno type="DOI">10.1007/978-3-642-13073-1_28</idno><idno type="ChapterID">28</idno><idno type="ChapterID">Chap28</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G) respectively, are conceptually linked to domination and independence numbers and have numerous relations to other graph parameters. It is a long-standing open question whether determining these numbers for a graph G on n vertices admits exact algorithms running in time less than the trivial Ω(2 n ) enumeration barrier. We solve this open problem by devising parameterized algorithms for the duals of the natural parameterizations of the problems with running times faster than $\mathcal{O}^*(4^{k})$ . For example, we present an algorithm running in time $\mathcal{O}^*(3.069^{k}))$ for determining whether IR(G) is at least n − k. Although the corresponding problem has been shown to be in FPT by kernelization techniques, this paper offers the first parameterized algorithms with an exponential dependency on the parameter in the running time. Furthermore, these seem to be the first examples of a parameterized approach leading to a solution to a problem in exponential time algorithmics where the natural interpretation as exact exponential-time algorithms fails.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>Australie</li><li>France</li></country><region><li>Centre-Val de Loire</li><li>Grand Est</li><li>Lorraine (région)</li><li>Rhénanie-Palatinat</li><li>Région Centre</li></region><settlement><li>Metz</li><li>Orléans</li><li>Trèves (Allemagne)</li></settlement><orgName><li>Université Paul Verlaine - Metz</li><li>Université de Trèves</li></orgName></list><tree><country name="Allemagne"><noRegion><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name></noRegion><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name></country><country name="Australie"><noRegion><name sortKey="Brankovic, Ljiljana" sort="Brankovic, Ljiljana" uniqKey="Brankovic L" first="Ljiljana" last="Brankovic">Ljiljana Brankovic</name></noRegion><name sortKey="Brankovic, Ljiljana" sort="Brankovic, Ljiljana" uniqKey="Brankovic L" first="Ljiljana" last="Brankovic">Ljiljana Brankovic</name></country><country name="France"><region name="Grand Est"><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name></region><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C69 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000C69 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:D53E1C54122748DE8921D66B3B2ABDDBDB118DD2
|texte= A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance
}}
| This area was generated with Dilib version V0.6.31. |  |